Interval List Intersections

LeetCode 1028 | Difficulty: Medium

Medium

Problem Description

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start~i~, end~i~] and secondList[j] = [start~j~, end~j~]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a = 1

- `0 <= start~i~ < end~i~ <= 10^9`

- `end~i~ < start~i+1~`

- `0 <= start~j~ < end~j~ <= 10^9 `

- `end~j~ < start~j+1~`

Topics: Array, Two Pointers, Sweep Line

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

---

Solutions

Solution 1: C# (Best: 160 ms)

Metric	Value
Runtime	160 ms
Memory	47.1 MB
Date	2022-01-28

Solution

public class Solution {
    public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) {
        int m = firstList.Length;
    int n = secondList.Length;
    int i = 0, j= 0;
    
    List<int[]> result = new List<int[]>();
    while(i<m && j<n)
    {
        int a_start = firstList[i][0];
        int a_end = firstList[i][1];
        int b_start = secondList[j][0];
        int b_end = secondList[j][1];
        if(a_start <= b_end && b_start <= a_end)
        {
            result.Add(new int[] { Math.Max(a_start, b_start), Math.Min(a_end, b_end)});
        }
        if(a_end <= b_end)
        {
            i++;
        }
        else j++;
        
    }
    return result.ToArray();
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.